#define  _CRT_SECURE_NO_WARNINGS
// class Solution {
// public:
//     int mp[31];
//     int fib(int n) {
//         return (n <= 1) ? n : mp[n] ? mp[n] : mp[n] = fib(n - 1) + fib(n - 2);
//     }
// };
class Solution {
public:
    int fib(int n) {
        int dp[31] = { 0, 1 };
        for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};